/**
  */

package org.rescue.Dag;

import java.util.*;

public class DirectedAcyclicGraph 
{
  // -----------------------------------------------------------------------
  //  Variables declarations
  // -----------------------------------------------------------------------

  /** Vector of nodes of the DAG. Nodes are of the type DAGNode. */
  protected Vector<DAGNode> nodes = new Vector<DAGNode>();

  /** Hashtable of nodes with concepts as keys and node indexes as values. */
  protected HashMap<Concept, Integer> nodesHash = new HashMap<Concept, Integer>();

  /** Is the graph level-based? */
  protected boolean levelBased = false;

  // -----------------------------------------------------------------------
  //  Constructor
  // -----------------------------------------------------------------------
  /**
   * Empty constructor.
   */
  public DirectedAcyclicGraph()
  {
  }

  // -----------------------------------------------------------------------
  //  Methods of taxonomy handling
  // -----------------------------------------------------------------------
  /**
   * Add a relationship to DAG.
   *
   * @param parent parent concept
   * @param child child concept
   * @exception DagException parent is child's child (cycle!)
   */
  public void addRelationship(Concept parent, Concept child, boolean checkCycle)
    throws DagException {

    if (parent == null) throw new DagException("parent is null");
    if (child == null)  throw new DagException("child is null");

    // Look for parent and child nodes:
    DAGNode par = findNodeOfConcept(parent);
    DAGNode cld = findNodeOfConcept(child);

    // Parent and child exist. Make sure there will be no cycle:
    if (par != null && cld != null) {

      // Parent is already assigned to child:
      if (cld.getParentIndex(par) >= 0)
        return;

      // Parent equals child:
      if ( par.equals(cld) )
        throw new DagException("Illegal relationship: parent and child are equal!");

      // Check for cycle:
      Vector grandpars = getAncestors( (Concept)par.getNodeValue() );
      for (int i = 0; i < grandpars.size(); i++) {
        Concept grandpa = (Concept) grandpars.elementAt(i);
        if ( grandpa.equals(child) )
          throw new DagException("Illegal relationship: parent is child's child!");
      };
    };

    // Child does not exist - create:
    if (cld == null) {
      cld = new DAGNode();
      cld.setNodeValue(child);
      cld.setLeaf(true);
      cld.setRoot(false);
      nodes.addElement(cld);
      nodesHash.put(child, nodes.size()-1 );
    };

    // Parent does not exist - create:
    if (par == null) {
      par = new DAGNode();
      par.setNodeValue(parent);
      par.setRoot(true);
      par.setLeaf(false);
      nodes.addElement(par);
      nodesHash.put( parent, nodes.size()-1 );
    };

    // Set relation:
    par.addChildNode(cld);
    par.setLeaf(false);
    par.setLevel(-1);

    cld.addParentNode(par);
    cld.setRoot(false);
    cld.setLevel(-1);

    levelBased = false;
  }

  /**
   * Returns number of relationships of DAG.
   *
   * @return number of relationships of DAG
   */
  public int getNumberOfRelationships() {

    int nrel = 0;
    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      nrel = nrel + chn.getParentsCount();
    };
    return nrel;
  }

  /**
   * Is current DAG level-based? If not, use method calcLevels to
   * create levels (if possible).
   *
   * @return true is level-based, false otherwise
   */
  public boolean isLevelBased() {

    return levelBased;
  }

  /**
   * Calculates all levels for the hierarchy nodes.
   *
   * @throws DagException graph is not level-based
   */
  public void calcLevels() throws DagException {

    calcLevels(false);
  }

  /**
   * Calculates all levels for the hierarchy nodes. If the parameter
   * 'anyway' is true, levels are calculated even if the graph is
   * not level-based. Otherwise, a corresponding exception is thrown.
   *
   * @param anyway calculate anyway
   * @throws DagException graph is not level-based for false 'anyway'
   */
  public void calcLevels(boolean anyway) throws DagException {

    // Init levels:
    Vector<DAGNode> roots = new Vector<DAGNode>();
    for (int i = 0; i < nodes.size(); i++) {
      DAGNode node = (DAGNode) nodes.elementAt(i);
      if ( node.isRoot() ) {
        node.setLevel(0);
        roots.addElement(node);
      }
      else
        node.setLevel(-1);
    }

    // Enter all roots and determine levels of their trees:
    for (int i = 0; i < roots.size(); i++) {
      DAGNode root = (DAGNode) roots.elementAt(i);
      calcNodeLevels(root, anyway);
    }

    levelBased = true;
  }

  /**
   * Determines levels of nodes by recursively calling this method.
   *
   * @param node parent node to traverse
   * @param anyway calculate anyway
   * @throws DagException DAG is not level-based for false 'anyway'
   */
  private void calcNodeLevels(DAGNode node, boolean anyway) throws DagException {

     int nodeLevel = node.getLevel();
     for (int i = 0; i < node.getChildCount(); i++) {
       DAGNode child = node.getChildAt(i);
       int childLevel = child.getLevel();
       if (childLevel == -1) {
         child.setLevel(nodeLevel + 1);
         calcNodeLevels(child, anyway);
       }
       else {
         if (!anyway && childLevel != nodeLevel + 1)
           throw new DagException("graph is not level-based");
       }
     };
  }

  /**
   * Get direct parents of a given child concept.
   *
   * @param child child concept
   * @return vector of direct parent conncept
   */
  public Vector<Concept> getParents(Concept child) {

    Vector<Concept> parCats = new Vector<Concept>();

    // Look for child node:
    DAGNode cld = findNodeOfConcept(child);

    // Node not found => no parents:
    if (cld == null)
      return parCats;

    // Return parents:
    for (int i = 0; i < cld.getParentsCount(); i++)
      parCats.addElement((Concept) cld.getParentAt(i).getNodeValue() );

    return parCats;
  }

  /**
   * Get direct children of a given parent.
   *
   * @param parent parent concept
   * @return vector of direct child concepts
   */
  public Vector<Concept> getChildren(Concept parent) {

    Vector<Concept> cldCats = new Vector<Concept>();

    // Look for child node:
    DAGNode par = findNodeOfConcept(parent);

    // Node not found => no children:
    if (par == null)
      return cldCats;

    // Return children:
    for (int i = 0; i < par.getChildCount(); i++)
      cldCats.addElement((Concept) par.getChildAt(i).getNodeValue() );

    return cldCats;
  }

  /**
   * Get all parents of a given child concept.
   *
   * @param child child concept
   * @return vector of all parent concept
   */
  public Vector<Concept> getAncestors(Concept child) {

    Vector<Concept> parCats = new Vector<Concept>();

    // Look for child node:
    DAGNode cld = findNodeOfConcept(child);

    // Node not found => no parents:
    if (cld == null)
      return parCats;

    // Get all parents recursively:
    Vector<DAGNode> allPars     = new Vector<DAGNode>();
    DAGNode node = cld;
    IntVector parup    = new IntVector();
    IntVector childown = new IntVector();
    parup.addElement(-1);
    childown.addElement(-1);
    int lev        = 0;
    boolean newpar = true;
    while (newpar) {
      int ipar = parup.IntegerAt(lev);
      if (ipar < node.getParentsCount() - 1) {
        ipar = ipar + 1;
        parup.setElementAt(ipar, lev);
        DAGNode par = node.getParentAt(ipar);
        if (allPars.indexOf(par) < 0) allPars.addElement(par);
        lev = lev + 1;
        if (parup.size() <= lev) {
          parup.addElement(-1);
          childown.addElement( par.getChildIndex(node) );
        }
        else {
          parup.setElementAt(-1, lev);
          childown.setElementAt( par.getChildIndex(node), lev );
        }
        node = par;
      }
      else {
        ipar = -1;
        parup.setElementAt(ipar, lev);
        if (lev > 0) {
          cld = node.getChildAt(childown.IntegerAt(lev));
          lev = lev - 1;
          node = cld;
        }
        else
          newpar = false;
      };
    }

    // Extract parent categories:
    for (int i = 0; i < allPars.size(); i++) {
      Concept parCat = (Concept) ((DAGNode) allPars.elementAt(i)).getNodeValue();
      if (parCats.indexOf(parCat) < 0) parCats.addElement(parCat);
    };

    return parCats;
  }

  /**
   * Get all children of a given parent.
   *
   * @param parent parent concept
   * @return vector of all child concepts
   */
  public Vector<Concept> getDescendants(Concept parent) {

    Vector<Concept> cldCats = new Vector<Concept>();

    // Look for child node:
    DAGNode par = findNodeOfConcept(parent);

    // Node not found => no children:
    if (par == null)
      return cldCats;

    // Get all children recursively:
    Vector<DAGNode> allClds     = new Vector<DAGNode>();
    DAGNode node = par;
    IntVector childown = new IntVector();
    IntVector parup    = new IntVector();
    childown.addElement(-1);
    parup.addElement(-1);
    int lev        = 0;
    boolean newcld = true;
    while (newcld) {
      int icld = childown.IntegerAt(lev);
      if (icld < node.getChildCount() - 1) {
        icld = icld + 1;
        childown.setElementAt(icld, lev);
        DAGNode cld = node.getChildAt(icld);
        if (allClds.indexOf(cld) < 0) allClds.addElement(cld);
        lev = lev + 1;
        if (childown.size() <= lev) {
          childown.addElement(-1);
          parup.addElement( cld.getParentIndex(node) );
        }
        else {
          childown.setElementAt(-1, lev);
          parup.setElementAt( cld.getParentIndex(node), lev );
        }
        node = cld;
      }
      else {
        icld = -1;
        childown.setElementAt(icld, lev);
        if (lev > 0) {
          par = node.getParentAt( parup.IntegerAt(lev) );
          lev = lev - 1;
          node = par;
        }
        else
          newcld = false;
      };
    };

    // Extract child categories:
    for (int i = 0; i < allClds.size(); i++) {
      Concept cldCat = (Concept) ((DAGNode) allClds.elementAt(i)).getNodeValue();
      if (cldCats.indexOf(cldCat) < 0) cldCats.addElement(cldCat);
    };

    return cldCats;
  }

  /**
   * Return all root nodes of the DAG.
   *
   * @return vector Concepts of all root nodes
   */
  public Vector<Concept> getAllRoots() {

    Vector<Concept> allRoots = new Vector<Concept>();

    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      if (chn.isRoot())
        allRoots.addElement((Concept)chn.getNodeValue());
    };

    return allRoots;
  }

  /**
   * Return all leaves nodes of the DAG.
   *
   * @return vector Concepts of all leaf nodes
   */
  public Vector<Concept> getAllLeafs() {

    Vector<Concept> allLeafs = new Vector<Concept>();

    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      if (chn.isLeaf())
        allLeafs.addElement((Concept)chn.getNodeValue());
    };

    return allLeafs;
  }

  /**
   * Return all parents of the given node which are roots.
   *
   * @param node specified node
   * @return all root nodes which are parents of node
   */
  public Vector<Concept> getAllRootParents(Concept node) {

    Vector<Concept> rpars = new Vector<Concept>();
    Vector<Concept> pars  = getAncestors(node);
    for (int i = 0; i < pars.size(); i++) {
      Concept parent = (Concept) pars.elementAt(i);
      if ( getNodeType(parent) == 0 )
        rpars.addElement(parent);
    }

    return rpars;
  }

  /**
   * Return all children of the given node which are leafs.
   *
   * @param node specified node
   * @return all leaf nodes which are children of node
   */
  public Vector<Concept> getAllLeafChildren(Concept node) {

    Vector<Concept> lchilds  = new Vector<Concept>();
    Vector<Concept> children = getDescendants(node);
    for (int i = 0; i < children.size(); i++) {
      Concept child = (Concept) children.elementAt(i);
      if ( getNodeType(child) == 2 )
         lchilds.addElement(child);
    }

    return lchilds;
  }

  /**
   * Get type of node (0 - root, 1 - intermediate, 2 - leaf).
   *
   * @param node node to check
   * @return type, -1 for unknown node
   */
  public int getNodeType(Concept node) {

    DAGNode mhn = findNodeOfConcept(node);
    if (mhn == null)
      return -1;

    if ( mhn.isRoot() )
      return 0;
    else if ( mhn.isLeaf() )
      return 2;
    else
      return 1;
  }

  /**
   * Get hierarchy level of node (0 - root).
   * ATTENTION: Only useful for level-based DAGs. Use method
   * isLevelBased to get this info.
   *
   * @param node node to check
   * @return type, -1 for unknown node
   */
  public int getNodeLevel(Concept node) {

    if (!levelBased) return -1;

    DAGNode mhn = findNodeOfConcept(node);
    if (mhn == null)
      return -1;

    return mhn.getLevel();
  }

  /**
   * Get all nodes of a given hierarchy level (0 - root).
   * ATTENTION: Only useful for level-based DAGs. Use method
   * isLevelBased to get this info.
   *
   * @param level hierarchy level
   * @return vector of all nodes of given level (Concepts of this level)
   */
  public Vector<Concept> getNodesOfLevel(int level) {

    Vector<Concept> allNodes = new Vector<Concept>();
    if (!levelBased) return allNodes;

    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      if (chn.getLevel() == level)
        allNodes.addElement((Concept) chn.getNodeValue() );
    };

    return allNodes;
  }

  /**
   * Show list of all relationsships of the form
   * parent - child.
   */
  public void printRelationships() {

    int ic = 0;
    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      for (int j = 0; j < chn.getParentsCount(); j++) {
        DAGNode par = (DAGNode) chn.getParentAt(j);
        System.out.println( ic++ + ": " + ((Concept)par.getNodeValue()).id + " <- " +
                           ((Concept)chn.getNodeValue()).id);
     };
    };
  }

  /**
   * Just for completeness.
   * Is the graph cyclic? The DAG may not contain cycles;
   * so it never should return true.
   *
   * @return true, if graph contains cycles, else false
   */
  protected boolean isCyclic() {

    for (int i = 0; i < nodes.size(); i++) {
      DAGNode chn = (DAGNode) nodes.elementAt(i);
      Concept node  = (Concept)chn.getNodeValue();
      Vector parents = getAncestors(node);
      for (int j = 0; j < parents.size(); j++) {
        Concept par = (Concept) parents.elementAt(j);
        if (par.equals(node))
          return true;
      };
    };

    return false;
  }

  /**
   * Find node of a given concept.
   *
   * @param concept concept
   * @return node of concept, null if not found
   */
  public DAGNode findNodeOfConcept(Concept concept) {

    Integer Nr = (Integer) nodesHash.get(concept);
    if (Nr == null)
      return null;

    int nr = Nr.intValue();
    DAGNode mhn = (DAGNode) nodes.elementAt(nr);

    return mhn;
  }

  public Enumeration<DAGNode> postOrder (Concept root) {
	  ArrayList<DAGNode> nodes = new ArrayList<DAGNode>();
	  DAGNode rootn = findNodeOfConcept(root);
	  if (rootn == null) return null;
	  traversePostorder (rootn,nodes);
	  return Collections.enumeration(nodes);
  }
  
  void traversePostorder(DAGNode node, ArrayList<DAGNode> nodes) {
	  Enumeration<DAGNode> list = node.children();
	  DAGNode chld;
	  if (list != null ) {
		  while (list.hasMoreElements()) {
			  chld = (DAGNode)list.nextElement();
			  traversePostorder(chld, nodes);
		  }
	  }
	  nodes.add(node);
  }  
 
  
  /*
   * Given a Concept object just its id set, return the instance 
   */
  public Concept findConcept(Concept c) {
	  return findNodeOfConcept(c).getNodeConcept();
  }
  
  // -----------------------------------------------------------------------
  //  Test
  // -----------------------------------------------------------------------
  /**
  * Main routine for testing.
  *
  * @param argv test arguments
  */
  public static void main(String[] argv) {

    try {
      DirectedAcyclicGraph cah = new DirectedAcyclicGraph();

      // Define concepts:
      Concept c1 = new Concept(1);
      Concept c2 = new Concept(2);
      Concept c3 = new Concept(3);
      Concept c4 = new Concept(4);
      Concept c5 = new Concept(5);
      Concept c6 = new Concept(6);
      Concept c7 = new Concept(7);
      Concept c8 = new Concept(8);
      Concept c9 = new Concept(9);
      Concept c10 = new Concept(10);
      Concept c11 = new Concept(11);
      Concept c12 = new Concept(12);
      Concept c13 = new Concept(13);
      Concept c14 = new Concept(14);
      Concept c15 = new Concept(15);
      Concept c16 = new Concept(16);
      Concept c17 = new Concept(17);
      Concept c18 = new Concept(18);
      Concept c19 = new Concept(19);
      Concept c20 = new Concept(20);
      Concept c21 = new Concept(21);
      Concept c22 = new Concept(22);

      // First subtree:
      cah.addRelationship(c1, c2,true);
      cah.addRelationship(c1, c3,true);
      cah.addRelationship(c3, c7,true);
      cah.addRelationship(c2, c4,true);
      cah.addRelationship(c2, c5,true);
      cah.addRelationship(c2, c6,true);
      cah.addRelationship(c4, c10,true);
      cah.addRelationship(c4, c11,true);
      cah.addRelationship(c4, c12,true);
      cah.addRelationship(c4, c13,true);
      cah.addRelationship(c7, c8,true);
      cah.addRelationship(c7, c9,true);
      cah.addRelationship(c12, c14,true);
      cah.addRelationship(c12, c15,true);

      // Second subtree:
      cah.addRelationship(c20, c21,true);
      cah.addRelationship(c20, c22,true);
      cah.addRelationship(c21, c12,true);
      cah.addRelationship(c21, c9,true);

      // This would lead to a cyclic graph and hence to an exception:
      // cah.addRelationship(c15, c1);

      // Print taxonomy:
      cah.printRelationships();
      System.out.println("numberOfRelationships = " + cah.getNumberOfRelationships());

      // Calculate levels:
      cah.calcLevels(true); // false would throw exception since not level-based!!

      // Get all root nodes:
      System.out.println("Roots:");
      Vector iv = cah.getAllRoots();
      for (int i = 0; i < iv.size(); i++)
       System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();

      // Get all leaf nodes:
      System.out.println("Leafs:");
      iv = cah.getAllLeafs();
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();

      // Get all nodes of given level (usually should not be used for this type of graphs):
      int level = 2;
      System.out.println("Nodes of level " + level + ":");
      iv = cah.getNodesOfLevel(level);
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();

      // Does graph contains cycles:
      System.out.println("isCyclic: " + cah.isCyclic());

      // Get type of node:
      Concept node = c20;
      System.out.println("node = " + node.id + " type = " +
                         cah.getNodeType(node));

      // Get layer of node (usually should not be used for this type of graphs):
      node = c9;
      System.out.println("node = " + node.id + " level = " +
                          cah.getNodeLevel(node));

      // Get parents of child:
      Concept child = c9;
      System.out.println("child = " + child.id + ":");

      iv = cah.getParents(child);
      System.out.print("parents -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();
      iv = cah.getAncestors(child);
      System.out.print("Ancestors -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();
      iv = cah.getAllRootParents(child);
      System.out.print("root parents -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();

      // Get children of parent:
      Concept parent = c21;
      System.out.println("parent = " + parent.id + ":");

      iv = cah.getChildren(parent);
      System.out.print("children -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();
      iv = cah.getDescendants(parent);
      System.out.print("Descendents -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();
      iv = cah.getAllLeafChildren(parent);
      System.out.print("leaf children -> ");
      for (int i = 0; i < iv.size(); i++)
        System.out.print(  ((Concept) iv.elementAt(i)).id + " ");
      System.out.println();
      
      System.out.println("POST ORDER");
      
      Enumeration<DAGNode> porder = cah.postOrder(c1);
      while (porder.hasMoreElements()) {
    	  DAGNode nde = porder.nextElement();
    	  System.out.print(((Concept)nde.getNodeValue()).id + " ");
      }      
    }
    catch (Exception ex) {
      ex.printStackTrace();
    };
  }
}